class Solution {
public:
    /**
     * @param n: an integer
     * @return: the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n
     */
     
    // int nextGreaterElement(int n) {
    //     string s = to_string(n);
    //     int len = s.length();
    //     for (int i = 0; i < len; ++i)
    //     {
    //         char tmp = s[len - i - 1];
    //         for (int j = i + 1; j < len; ++j)
    //         {
    //             if (s[len - j - 1] < tmp)
    //             {
    //                 // swap(s[len - j - 1], tmp); 这个是用tmp的值替换前面的值，不是交换
    //                 swap(s[len - j - 1], s[len - i - 1]);
    //                 return stoi(s);
    //             }
    //         }
    //     }
    //     return -1; 
    // }
// 错的
// Input
// 12321
// Output
// 22311
// Expected
// 13122


// 方法跟下一个排列相似
// 从最后一个位置开始，找到一个上升点，上升点之前的无需改动。
// 然后，翻转上升点之后的降序。
// 在降序里，找到[第一个比上升点大的]，交换位置。
    int toInt(string s)
    {
        int result = 0;
        // for (int i = s.length() - 1; i >= 0; --i)
        for (int i = 0; i < s.length(); ++i)
        {
            // if (((result * 10 + (s[i] - '0')) ^ result) < 0) return -1;
            if (result * 10 + (s[i] - '0') < result) return -1;
            result = result * 10 + (s[i] - '0'); 
            cout << result << endl;
        }
        return result;
    }
    int nextGreaterElement(int n) {
        string s = to_string(n);
        for (int i = s.length() - 2; i >= 0; --i)
        {
            if (s[i] < s[i + 1])
            {
                // swap(s[i], s[i + 1]);//不是直接交换这两个，而是第一个比s[i]大的
                string str1 = s.substr(0, i + 1);
                string str2 = s.substr(i + 1);
                reverse(str2.begin(), str2.end());
                s = str1 + str2;
                for (int j = i + 1; j < s.length(); ++j)
                {
                    if (s[j] > s[i]) 
                    {
                        swap(s[i], s[j]);
                        break;
                    }
                }
                // return stoi(s); 可能越界
                return toInt(s);
            }
        }
        return -1;
    }
};